{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 单词量大的时候，单词与单词间的比较比较耗时，所以先建立完整的的邻接表再广度优先搜索耗时也多，\n",
    "# 可以在广度搜索的时候再找边，还可利用双向搜索进行优化。\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if endWord not in wordList:\n",
    "            return 0\n",
    "        l = len(endWord)\n",
    "        ws = set(wordList)\n",
    "        head = {beginWord}\n",
    "        tail = {endWord}\n",
    "        tmp = list('abcdefghijklmnopqrstuvwxyz')\n",
    "        res = 1\n",
    "        while head:\n",
    "            if len(head) > len(tail):\n",
    "                head, tail = tail, head\n",
    "            q = set()\n",
    "            for cur in head:\n",
    "                for i in range(l):\n",
    "                    for j in tmp:\n",
    "                        word = cur[:i] + j + cur[i+1:]\n",
    "                        if word in tail:\n",
    "                            return res + 1\n",
    "                        if word in ws:\n",
    "                            q.add(word)\n",
    "                            ws.remove(word)\n",
    "            head = q\n",
    "            res += 1 \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:\n",
    "        if(endWord not in wordList):\n",
    "            return 0\n",
    "        if(beginWord not in wordList):\n",
    "            wordList.append(beginWord)\n",
    "        # 建立邻接表\n",
    "        wordSet = set(wordList)\n",
    "        vertexs = [set() for x in range(len(wordList))] # !!!不要写成[set()]*n\n",
    "        alphaList = [chr(x) for x in range(ord('a'), ord('z')+1)]\n",
    "        wordMap = {wordList[i]:i for i in range(len(wordList))}\n",
    "        n = len(beginWord)\n",
    "        for h in range(len(wordList)):\n",
    "            w = wordList[h]\n",
    "            for i in range(n):\n",
    "                for w2 in [ w[0:i] + x + w[i+1:] for x in alphaList ]:\n",
    "                    if(w2 in wordSet):\n",
    "                        vertexs[h].add(wordMap[w2])\n",
    "        # 广度优先搜索最短路径\n",
    "        visited = [False] * len(wordList)\n",
    "        queue = [wordMap[beginWord]]\n",
    "        visited[wordMap[beginWord]] = True\n",
    "        depth = 0\n",
    "        head = 0\n",
    "        while(head < len(queue)):\n",
    "            depth += 1\n",
    "            rear = len(queue)\n",
    "            for i in queue[head:rear]:\n",
    "                w = wordList[i]\n",
    "                if(w == endWord): # 找到目标\n",
    "                    return depth\n",
    "                for i2 in vertexs[i]:\n",
    "                    if(visited[i2] == False):\n",
    "                        queue.append( i2 )\n",
    "                        visited[i2] = True\n",
    "            head = rear\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n"
     ]
    }
   ],
   "source": [
    "beginWord = \"hit\"\n",
    "endWord = \"cog\"\n",
    "wordList = [\"hot\",\"dot\",\"dog\",\"lot\",\"log\",\"cog\"]\n",
    "\n",
    "\n",
    "#beginWord = \"hit\"\n",
    "#endWord = \"cog\"\n",
    "#wordList = [\"hot\",\"dot\",\"dog\",\"lot\",\"log\"]\n",
    "\n",
    "#beginWord = \"hot\"\n",
    "#endWord = \"dog\"\n",
    "#wordList = [\"hot\",\"dog\",\"dot\"]\n",
    "\n",
    "#beginWord = \"a\"\n",
    "#endWord = \"c\"\n",
    "#wordList = [\"a\",\"b\",\"c\"]\n",
    "\n",
    "\"a\", \"c\",\n",
    "[\"a\",\"b\",\"c\"]\n",
    "\n",
    "a = Solution()\n",
    "\n",
    "print(a.ladderLength(beginWord, endWord, wordList))\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
